package top.minuy.subject.leetcode._1147;

/**
 * 使用哈希实现字符串比较的比较
 * <p>
 * 1147. 段式回文
 * 段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。
 * <p>
 * 举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。
 * <p>
 * <p>
 * <p>
 * 给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。
 * <p>
 * 如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：
 * <p>
 * 每个 a_i 都是一个非空字符串；
 * 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；
 * 对于所有1 <= i <= k，都有 a_i = a_{k+1 - i}。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：text = "ghiabcdefhelloadamhelloabcdefghi"
 * 输出：7
 * 解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。
 * 示例 2：
 * <p>
 * 输入：text = "merchant"
 * 输出：1
 * 解释：我们可以把字符串拆分成 "(merchant)"。
 * 示例 3：
 * <p>
 * 输入：text = "antaprezatepzapreanta"
 * 输出：11
 * 解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。
 * 示例 4：
 * <p>
 * 输入：text = "aaa"
 * 输出：3
 * 解释：我们可以把字符串拆分成 "(a)(a)(a)"。
 * <p>
 * <p>
 * 提示：
 * <p>
 * text 仅由小写英文字符组成。
 * 1 <= text.length <= 1000
 * 通过次数4,238提交次数7,534
 *
 * @author Minuy
 * @time 17:31
 * @date 2021/11/12
 */
public class Solution2 {
    private static final long MOD = (long) (1e9 + 7);
    private long[] pow26;

    public int longestDecomposition(String text) {
        pow26 = new long[text.length() / 2 + 1];
        pow26[0] = 1;
        for (int i = 1; i < pow26.length; i++) {
            pow26[i] = (pow26[i - 1] * 26) % MOD;
        }
        return solve(text, 0, text.length() - 1);
    }

    // 找text中[left,right]的段回文个数
    private int solve(String text, int left, int right) {
        if (left > right) { // 等于不能回0，中间一个算一段
            return 0;
        }

        long preHash = 0, postHash = 0;

        // [left+i, right-j]
        for (int i = left, j = right; i < j; i++, j--) {

            preHash = (preHash * 26 + (text.charAt(i) - 'a')) % MOD;
            postHash = ((text.charAt(j) - 'a') * pow26[right - j] + postHash) % MOD;

            if (preHash == postHash) { // 判断hash值相不相等，下面的判断对付哈希冲突
                // text 中 [left, i] 与 [j, right] 是否相等
                if (equal(text, left, i, j, right)) {
                    return 2 + solve(text, i + 1, j - 1);
                }
            }
        }
        return 1;
    }

    // 判断text中，[l1,r1] 与  [l2,r2] 是否相等，段1长度等于段2长度
    private boolean equal(String text, int l1, int r1, int l2, int r2) {
        for (int i = l1, j = l2; i <= r1; i++, j++) {
            if (text.charAt(i) != text.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}
